package com.ieslab.dynamicp;

import java.util.HashMap;
import java.util.Map;

/**
 * 最长公共字符子序列
 */
public class LongestCommonSubstring {
	private static Map<Integer, String> strMap = new HashMap<Integer, String>();
	private static char[] str = null;
	static {
		strMap.put(1, "ABCBDAB");
		strMap.put(2, "BDCABA");
	}

	public static void main(String[] args) {
		System.out.println("输入两个字符产");
		int m = strMap.get(1).length();
		int n = strMap.get(2).length();
		int[][] c = new int[m + 1][n + 1]; // c[i][j]存储序列a0a1...a(i-1)和序列b0b1...b(j-1)的最长公共子序列的长度
		int k = lcs_len(c, m, n);
		str = new char[k];
		buile_lcs(k, m, n, c);
		System.out.println(str);
	}

	/**
	 * 计算最优值
	 */
	private static int lcs_len(int[][] c, int i, int j) {
		int t1 = 0, t2 = 0;
		if (i == 0 || j == 0) {
			c[i][j] = 0;
		} else if (strMap.get(1).charAt(i - 1) == strMap.get(2).charAt(j - 1)) {
			c[i][j] = lcs_len(c, i - 1, j - 1) + 1;
		} else {
			t1 = lcs_len(c, i, j - 1);
			t2 = lcs_len(c, i - 1, j);
			if (t1 > t2) {
				c[i][j] = t1;
			} else {
				c[i][j] = t2;
			}
		}
		return c[i][j];
	}

	/**
	 * 构造最长公共子序列
	 */
	private static void buile_lcs(int k, int i, int j, int[][] c) {
		if (i == 0 || j == 0) {
			return;
		}
		if (c[i][j] == c[i - 1][j]) {
			buile_lcs(k, i - 1, j, c);
		} else if (c[i][j] == c[i][j - 1]) {
			buile_lcs(k, i, j - 1, c);
		} else {
			str[k - 1] = strMap.get(1).charAt(i - 1); // i-1,k-1为数组下标(0-base)
			buile_lcs(k - 1, i - 1, j - 1, c);
		}
	}
}
